﻿#define  _CRT_SECURE_NO_WARNINGS 1

/*
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
*/

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);

//栈顶插入数据
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//取栈顶数据

int StackSize(ST* ps);//数据个数
bool StackEmpty(ST* ps);//判断是不是空

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//栈空了，调用top，直接中止程序报错
	assert(ps->top > 0);
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	//栈空了，调用top，直接中止程序报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

bool isValid(char* s)
{
	ST st;
	StackInit(&st);
	while (*s != '\0')
	{
		switch (*s)
		{
			case '{':
			case '[':
			case '(':
				{
					StackPush(&st, *s);
					++s;
					break;
				}
			case '}':
			case ']':
			case ')':
				{
				if (StackEmpty(&st))
				{
					StackDestory(&st);
					return false;
				}
					char top = StackTop(&st);
					StackPop(&st);
					//不匹配
					if ((*s == '}' && top != '{')
						|| (*s == ']' && top != '[')
						|| (*s == ')' && top != '('))
					{
						StackDestory(&st);
						return false;
					}
					else
					{
						++s;
					}
					break;
				}
			default:
				break;
		}
	}
	bool ret = StackEmpty(&st);
	StackDestory(&st);
	return ret;
}